package org.example.leetcpde;

import com.google.common.util.concurrent.RateLimiter;
import org.junit.jupiter.api.Test;

import java.util.*;

public class Leetcode
        implements IArray, IListNode {

    @Test
    void twoSum() {
        int[] nums = parse("[3,2,4]");
        int[] ints = twoSum(nums, 6);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    public int[] twoSum(int[] nums,
                        int target) {
        Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            idx.put(n, i);
        }

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int retain = target - num;
            if (idx.containsKey(retain) && idx.get(retain) != num) {
                return new int[]{i, idx.get(retain)};
            }


        }

        return new int[2];
    }

    @Test
    void addTwoNumbers() {
        ListNode l1 = new ListNode().fill("[9,9,9,9,9,9,9]");
        ListNode l2 = new ListNode().fill("[9,9,9,9]");
        ListNode node = addTwoNumbers(l1, l2);
        System.out.println(22);
    }

    public ListNode addTwoNumbers(ListNode l1,
                                  ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tail = head;

        int step = 0;

        for (; ; ) {
            if (l1 == null || l2 == null) {
                break;
            }

            int sum = l1.val + l2.val + step;
            tail.next = new ListNode(sum % 10);
            step = sum / 10;

            l1 = l1.next;
            l2 = l2.next;
            tail = tail.next;
        }

        ListNode retain = l1 == null ? l2 : l1;

        while (retain != null) {
            int sum = retain.val + step;
            tail.next = new ListNode(sum % 10);
            step = sum / 10;
            retain = retain.next;
            tail = tail.next;
        }

        if (step != 0) {
            tail.next = new ListNode(1);
        }

        return head.next;
    }

    @Test
    void lengthOfLongestSubstring() {
        String aa = "aabaab!bb";
        System.out.println(lengthOfLongestSubstring(aa));
    }

    public int lengthOfLongestSubstring(String s) {
        byte[] bytes = s.getBytes();
        BitSet bitSet = new BitSet();
        int max = 0;
        for (int i = 0, j = 0; j < bytes.length; j++) {
            byte aByte = bytes[j];
            for (; bitSet.get(aByte); ) {
                bitSet.clear(bytes[i++]);
            }

            bitSet.set(aByte);
            max = Math.max(max, j - i + 1);
        }

        return max;
    }

    @Test
    void findMedianSortedArrays() {
        int[] nums1 = parse("[100001]");
        int[] nums2 = parse("[100000]");
        findMedianSortedArrays(nums1, nums2);
    }

    public double findMedianSortedArrays(int[] nums1,
                                         int[] nums2) {

        int len1 = nums1.length;
        int len2 = nums2.length;
        int totalLen = len1 + len2;
        int midIdx = totalLen >> 1;
        boolean isOdd = (totalLen & 1) == 1;

        int[] val = new int[2];
        int i = 0, j = 0;
        for (int count = 0; count <= midIdx; count++) {
            if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {
                val[count % 2] = nums1[i];
                i++;
            } else {
                val[count % 2] = nums2[j];
                j++;
            }
        }

        if (isOdd) {
            return Math.max(val[0], val[1]);
        }

        return (val[0] + val[1]) / 2.0;
    }

    @Test
    void findMedianSortedArraysV2() {
        //        int[] nums1 = parse("[1]");
        //        int[] nums2 = parse("[2,3,4,5,6]");
        int[] nums1 = parse("[1,4]");
        int[] nums2 = parse("[2,3,5,6]");

        double medianSortedArraysV3 = findMedianSortedArraysV2(nums1, nums2);
        System.out.println(medianSortedArraysV3);
    }

    public double findMedianSortedArraysV2(int[] nums1,
                                           int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int total = len2 + len1;
        int halfNum = (total + 1) >> 1;
        boolean isOdd = (total & 1) == 1;
        int n1 = getKthElement(nums1, nums2, halfNum);
        if (isOdd) {
            return n1;
        }

        int n2 = getKthElement(nums1, nums2, halfNum + 1);
        return (n1 + n2) / 2.0;
    }

    public int getKthElement(int[] nums1,
                             int[] nums2,
                             int k) {
        for (int i = 0, j = 0, len1 = nums1.length, len2 = nums2.length, used; ; ) {
            if (i == len1) {
                return nums2[j + k - 1];
            }

            if (j == len2) {
                return nums1[i + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[i], nums2[j]);
            }

            int halfCnt = k >> 1;
            int i2 = Math.min(len1, i + halfCnt) - 1;
            int j2 = Math.min(len2, j + halfCnt) - 1;

            if (nums1[i2] <= nums2[j2]) {
                used = i2 - i + 1;
                i = i2 + 1;
            } else {
                used = j2 - j + 1;
                j = j2 + 1;
            }
            k -= used;
        }
    }
}
